package link;

import array.ListNode;

public class PartitionList86 {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode resultHead = new ListNode();
        ListNode less = resultHead;
        ListNode idle = new ListNode();
        idle.next = head;
        ListNode pre = idle;
        while (pre != null && pre.next != null) {
            if (pre.next.val < x) {
                less.next = pre.next;
                less = less.next;
                pre.next = pre.next.next;
            } else {
                pre = pre.next;
            }

        }
        less.next = idle.next;
        return resultHead.next;
    }
}
